package leetcode.year2021.month11;

import java.util.Arrays;
import java.util.HashMap;

// 560. 和为 K 的子数组
public class _11_3SubarraySum560 {
  // 使用前缀和 + 哈希表优化
  public int subarraySum(int[] nums, int k) {
    int n = nums.length;
    int ans = 0;
    HashMap<Integer, Integer> mp = new HashMap<>();
    mp.put(0,1);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += nums[i];

      ans += mp.getOrDefault(sum-k,0);

      Integer count = mp.getOrDefault(sum, 0);
      mp.put(sum,count+1);

    }
    return ans;
  }

//  // 暴力枚举解法
//  public int subarraySum(int[] nums, int k) {
//    int ans = 0;
//    int n = nums.length;
//    for (int i = 0; i < n; i++) {
//      int sum = 0;
//      for (int j = i; j < n; j++) {
//        sum += nums[j];
//        if (sum == k){
//          ans++;
//        }
//      }
//    }
//    return ans;
//  }

  /**
   * 560. 和为 K 的子数组
   * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
   *
   * 示例 1：
   *
   * 输入：nums = [1,1,1], k = 2
   * 输出：2
   * 示例 2：
   *
   * 输入：nums = [1,2,3], k = 3
   * 输出：2
   *
   *
   * 提示：
   *
   * 1 <= nums.length <= 2 * 104
   * -1000 <= nums[i] <= 1000
   * -107 <= k <= 107
   */
}
